package Count;

import org.w3c.dom.Node;

import java.util.HashMap;

public class CopyLink {
    //复制带随机指针的链表
    static class Node{
        int val;
        Node next;
        Node random;
        public Node(int val){
            this.val=val;
            this.next=null;
            this.random=null;
        }
    }
    public Node copyLink(Node head){
        HashMap<Node,Node> map=new HashMap<>();
        Node cur=head;
        while(cur!=null){
            Node node=new Node(cur.val);//创建新节点作为val,节点复合
            map.put(cur,node);
            cur=cur.next;
        }
        cur=head;
        while(cur!=head){
            map.get(cur).next=map.get(cur.next);//连接新节点
            map.get(cur).random=map.get(cur.random).random;
            cur=cur.next;
        }
        return head;
    }
    public void display(Node head){
        Node cur=head;
        while(cur.next!=null){
            System.out.println("key；"+cur.val+",new Node:"+cur.next.val+",random node:"+cur.random.val);
            cur=cur.next;
        }
    }
}
